package 剑指offer.递归与回溯;

/**
 * 斐波那契数列公式：
 *
 *        | 0   n=0
 *        | 1   n=1
 * f(n) = <
 *        | f(n-1) + f(n-2)  n>1
 *
 * 很多问题都是《斐波那契数列》问题的变形，例如跳台阶问题：一次可以跳1或2个台阶，求跳上n阶台阶共有几种跳法
 *
 * 第一次跳 1 个，剩下 n-1 个可跳
 * 第一次跳 2 个，剩下 n-2 个可跳
 * 所以 n > 2 时 f(n) = f(n-1) + f(n-2)
 */
public class 第10题裴波那契数列 {

    /**
     * 求斐波那契数列的第 N 项
     *
     *
     * 一般的解法就是递归，如下所示。
     * 但是他有一个很严重的问题就是存在大量的重复计算，随着 n 增大，计算越来越慢
     * @param n 求解谁的数列
     * @return
     */
    public static int fib(int n) {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        return fib(n - 1) + fib(n - 2);
    }

    /**
     * 遇到这种递归问题时：存在大量重复计算
     * 好的解决办法就是自底向上，使用循环解决
     *
     * 事实上，能用递归处理的全部可以用循环代替，但是递归更容易编写
     * 平时还是以递归优先，出问题再替换算法
     * @param n
     * @return
     */
    public static int fibonacci(int n) {
        int[] ans = {0, 1};
        if (n < 1)
            return ans[n];
        // 先计算最小的模块，然后逐渐往上拼凑出答案。
        // 我把公式里面 f(n-1) 叫做左边，f(n-2) 叫做右边
        int left = 1;
        int right = 0;
        int result = 0;
        for (int i = 2; i <= n; i++) {
            // 从 2 开始算的话 f2 = f1 + f0，我把 f1 取名为 left，f2 取名为 right
            result = left + right;
            // 暂存本次结果，给下一次计算使用
            right = left;
            left = result;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(fib(4));
//        System.out.println(fib(31) == fibonacci(31));
    }
}
